/**
 * 从左往右扫的话，字符后面是否跟着星号会影响结果，分析起来有点复杂
 * 选择从右往左扫，星号的前面肯定有一个字符，星号也只影响这一个字符，它就像一个拷贝器
 * 情况1：s[i - 1] 和 p[j - 1] 是匹配的
 * 最右端的字符是匹配的，那么判断剩余子串是否匹配
 * 情况2：s[i - 1] 和 p[j - 1] 是不匹配的
 * 右端不匹配，还不能判死刑，可能是 p[j - 1] 为星号造成的不匹配，星号不是真实字符，它不匹配
 * 不算数，如果 p[j - 1] 不是星号，那就真的不匹配的了，所以又衍生出两种情况
 * 1. p[j - 1] == "*" && s[i - 1] == p[j - 2]，又需要考虑三种情况
 *    - p[i - 1] 星号可以让 p[j - 2] 在 p 子串里消失，出现 1 次，出现 >= 2 次
 *    - 只要其中一种使得剩余子串能匹配，那就能匹配
 * 2. p[j - 1] == "*", 但 s[i - 1] 和 p[j - 2] 不匹配
 * 还有救，p[j - 1] 星号可以干掉 p[j - 2]，继续考察 s[0, i - 1] 和 p[0, j - 3];
 */

var isMatch = function(s, p) {
  if (s == null || p == null) return false;
  const sLen = s.length, pLen = p.length;
  const dp = new Array(sLen + 1);
  for (let i = 0; i < dp.length; i++) {
    dp[i] = new Array(pLen + 1).fill(false); // 默认为 false
  }
  dp[0][0] = true;
  for (let j = 1; j < pLen + 1; j++) {
    if (p[j - 1] == "*") {
      dp[0][j] = dp[0][j - 2];
    }
  }

  // 迭代
  for (let i = 1; i < sLen + 1; i++) {
    for (let j = 1; j < pLen + 1; j++) {

      if (s[i - 1] == p[j - 1] || p[j - 1] == '.') {
        dp[i][j] = dp[i - 1][j - 1];
      } else if (p[j - 1] == "*") {
        if (s[i - 1] == p[j - 2] || p[j - 2] == '.') {
          dp[i][j] = dp[i][j - 2] || dp[i - 1][j - 2] || dp[i - 1][j];
        } else {
          dp[i][j] = dp[i][j - 2];
        }
      }
    }
  }
  return dp[sLen][pLen];
}
